package nl.rug.jvleusen.datastructurelib.set;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import nl.rug.jvleusen.datastructurelib.ISet;

/**
 * Set is an abstraction over a normal array that enforces the fact that an
 * object can be present only once, this implementation does not allow adding of {@code null}
 * and will resize as required.
 *
 * @author Jeroen van Leusen
 */
public class Set<E> implements ISet<E> {

    private E[] array;
    int size = 0;

    /**
     * Creates a set of the default size (16)
     */
    public Set() {
        this(16);
    }

    /**
     * Creates a set with the specified size.
     * @param size Initial size of the set.
     */
    public Set(int size) {
        array = (E[]) new Object[size];
    }

    /**
     * Initializes a set with the elements of the specified collection.
     * @param c Collection to build the set from.
     */
    public Set(Collection<? extends E> c) {
        this(c.size());
        addAll(c);
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> union(ISet<E> set2) {
        Set<E> set = new Set<E>(this);
        set.addAll(set2);
        return set;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> intersection(ISet<E> set2) {
        Set<E> set = new Set<E>(this);
        set.retainAll(set2);
        return set;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> difference(ISet<E> set2) {
        Set<E> set = (Set<E>) union(set2);
        set.removeAll(intersection(set2));
        return set;
    }

    /**
     * {@inheritDoc}
     */
    public boolean subset(ISet<E> set2) {
        Set<E> set = (Set<E>) intersection(set2);
        return set.containsAll(set2);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean contains(Object o) {
        return indexFor(o) != -1;
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {

            int currentCursor = -1;
            int nextCursor = findNextElement(currentCursor);

            public boolean hasNext() {
                return nextCursor != array.length;
            }

            public E next() {
                if (nextCursor == array.length) {
                    throw new NoSuchElementException();
                }
                currentCursor = nextCursor;
                nextCursor = findNextElement(currentCursor);
                return array[currentCursor];
            }

            public void remove() {
                if (currentCursor == -1) {
                    throw new IllegalStateException();
                }
                array[currentCursor] = null;
                size--;
                currentCursor = -1;
            }
        };
    }

    public Object[] toArray() {
        Object[] result = new Object[size()];
        int cursor = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null) {
                result[cursor++] = array[i];
            }
        }
        return result;
    }

    public <T> T[] toArray(T[] a) {
        if (a.length < size()) {
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
        }

        Object[] result = a; //Mask to allow adding of any object, will throw ArrayStoreException if it doesn't fit.
        int cursor = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null) {
                result[cursor++] = array[i];
            }
        }

        return a;
    }

    public boolean add(E e) {
        if (e == null) {
            throw new NullPointerException("add(null) is not supported.");
        }
        if (contains(e)) {
            return false;
        }

        if (size() == array.length) {
            resize(size() * 2);
        }
        int cursor = 0;

        while (array[cursor] != null) {
            cursor++;
        }

        //At this point array[cursor] == null
        array[cursor] = e;
        size++;
        return true;
    }

    public boolean remove(Object o) {
        if (o == null) {
            throw new NullPointerException("remove(null) is not supported.");
        }
        int index = indexFor(o);
        if (index == -1) {
            return false;
        }

        array[index] = null;
        size--;
        return true;
    }

    public boolean containsAll(Collection<?> c) {
        for (Object e : c) {
            if (!contains(e)) {
                return false;
            }
        }
        return true;
    }

    public boolean addAll(Collection<? extends E> c) {
        if (array.length < c.size()) {
            resize((int) (c.size() * 1.2)); //Ensure that under most circumstances it should fit.
        }

        boolean modified = false;

        for (E element : c) {
            if (add(element)) {
                modified = true;
            }
        }

        return modified;
    }

    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        for (Object o : c) {
            if (remove(o)) {
                modified = true;
            }
        }

        return true;
    }

    public boolean retainAll(Collection<?> c) {
        for (E element : this) {
            if (!c.contains(element)) {
                remove(element);
            }
        }
        return true;
    }

    public void clear() {
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        array = (E[]) new Object[16]; //Shrink back to default size.
        size = 0;
    }

    private int indexFor(Object o) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] != null && array[i].equals(o)) {
                return i;
            }
        }
        return -1;
    }

    private int findNextElement(int cursor) {
        cursor++;
        while (cursor != array.length) {
            if (array[cursor] != null) {
                return cursor;
            }
            cursor++;
        }
        return cursor;
    }

    private void resize(int size) {
        E[] newArray = (E[]) new Object[size];
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }
}
